#include <stdio.h>
#include <malloc.h>
#include"..\Stack\zyf_Stack.h"
#define MAX_SIZE 100
#define MAX_NODE 50
#define OK 1
#define ERROR 2
typedef int ElmeType
typedef int Status

typedef struct btthrnode
{
	ElmeType BtThrNode *Lchild,*Rchild;
	int Ltag,Rtag;
}BtThrNode;



/*
	构建线索化二叉树
	添加一个头结点
	需要几下遍历过程访问结点的先后顺序
	1.遍历过程中,附设指针last,并始终保持指针last指向
	当前访问的、指针p所指结点的前驱
	2.对一棵线索二叉树既可以从头结点也可以最后一个点开
	始按寻找直接后继进行遍历
	3.不需要堆栈
*/

//先序构造线索化二叉树
void perorderThreading(BtThrNode *T)
{
	BtThrNode *stack[MAX_NODE];
	BtThrNode *last = NULL,*p;//last始终是p前一个结点
	int top = 0;

	if (T != NULL)
	{
		stack[++top] = T;
		while (top > 0)
		{
			p = stack[top--];

			if (p -> Lchild != NULL)
				p -> Ltag = 0;
			else
			{
				p -> Ltag = 1;
				p -> Lchild = last;
			}

			if (last != NULL)
			{
				if (last -> Rchild != NULL)
					last -> Rtag = 0;
				else
				{
					last -> Rtag = 1;
					last -> Rchild = p;
				}
			}

			last = p;

			if (p -> Rchild != NULL)i
				stack[++top] = p -> Rchild;
			if (p -> Lchild != NULL)
				stack[++top] = p -> Lchild;

		}

		last -> Rtag = 1;
	}
}

//中序构造 线索化二叉树  algorithm
void inorderThreading(BtThrNode *T)
{
	BtThrNode *stack[MAX_NODE];
	BtThrNode *last = NULL, *p = T;
	int top = 0;

	while (p != NULL || top > 0)//循环条件与先序多了一个p判断
	{
		if (p != NULL)
		{
			stack[++top] = p;
			p = p -> Lchild;
		}
		else
		{
			p = stack[top--];

			if (p -> Lchild != NULL)
				p -> Ltag = 0;
			else
			{
				p -> Ltag = 1;
				p -> Lchild = last;
			}

			if (last != NULL)
			{
				if (last -> Rchild != NULL)
					last -> Rtag = 0;
				else
				{
					last -> Rtag = 1;
					last -> Rchild = p;
				}

			}

			last = p;
			p = p -> Rchild;
		}
	}

	last -> Rtag = 1;
}


//先序线索二叉树的先序遍历
void preorderThread(BtThrNode *T)
{
	BtThrNode *p = T;

	while (p != NULL)
	{
		visit(p -> data);

		if (p -> Ltag == 0)
			p = p -> Lchild;
		else
			p = p -> Rchild;
	}
}

//中序线索二叉树的中序遍历
void inorderThread(BtThrNode *T)
{
	BtThrNode *p;
	if (T != NULL)
	{
		p = T;
		while (p -> Ltag ==0)
		{
			p = p -> Lchild;
		}

		while (p != NULL)
		{
			visit(p -> data);

			if (p -> Rtag == 1)
				p = p -> Rchild;
			else
			{
				p = p -> Rchild;

				while(p -> Ltag == 0)
				{
					p = p -> Lchild;
				}
			}
		}
	}
}